Wędrowni treserzy pcheł
Limit pamięci: 32 MB
W Bajtocji można spotkać wędrownych treserów pcheł.
Tresowane pchły uczone są tańca, polegającego na wykonywaniu
precyzyjnych skoków w rytm muzyki.
Dokładnie wygląda to tak:
treser układa na stole w rządku ponumerowane żetony,
przy czym żetony nie muszą być ułożone po kolei.
Na każdym żetonie, oprócz jego numeru, jest również napisany numer żetonu,
na który powinna z niego skoczyć pchła.
Następnie treser ustawia po jednej pchle na każdym z żetonów i
włącza muzykę.
Na początku każdego taktu, każda z pcheł
wykonuje skok wprost na żeton, którego numer
jest napisany na żetonie, na którym w danej chwili stoi.
W trakcie tańca może się zdarzyć, że kilka pcheł znajdzie się na tym
samym żetonie i razem wykonują dalsze skoki.
Załóżmy, że mamy tresowanych pcheł i żetonów.
Jeśli podamy, jakie liczby znajdują się kolejno na żetonach numer
, to jednoznacznie opiszemy układ
choreograficzny, jaki zaprezentują pchły.
Jednak może się okazać, że dwa różne zestawy żetonów
dają ten sam układ, jeśli tylko odpowiednio je ułożymy.
Przykład
Powiedzmy, że mamy trzy żetony.
Jeśli z żetonu nr 1 należy skoczyć na żeton nr 2,
z żetonu nr 2 na żeton nr 3, a z żetonu nr 3 na żeton nr 1
(w skrócie: ),
to pchły będą tańczyć "w kółko"
i żadne dwie nigdy się nie spotkają na tym samym żetonie.
Jest to inny układ tańca, niż np.
,
gdzie już po dwóch taktach wszystkie trzy pchły spotkają się
na żetonie nr 3 i dalej będą razem skakać w miejscu.
Natomiast układy
oraz
są takie same -
wystarczy ułożyć żetony na stole w rzędzie,
w pierwszym przypadku w kolejności od lewej do prawej,
a w drugim od prawej do lewej, a pchły odtańczą ten sam taniec.
Zadanie
Gawiedź bardzo się niecierpliwi, gdy pchły tańczą według
tego samego układu więcej niż raz.
Dlatego potrzebny jest program, który:
-
wczyta ze standardowego wejścia liczbę przypadków testowych,
-
dla każdego z przypadków wczyta ze standardowego wejścia opis dwóch zestawów
żetonów i rozstrzygnie, czy żetony z tych zestawów można
ułożyć na stole tak, by pchły wykonały taki sam taniec,
-
wypisze odpowiedzi na standardowe wyjście.
Wejście
W pierwszym wierszu pliku tekstowego standardowego wejścia znajduje się
jedna liczba całkowita równa liczbie przypadków testowych,
.
Kolejne wiersze standardowego wejścia opisują kolejne przypadki
testowe -
każdy przypadek zajmuje trzy kolejne wiersze pliku.
Pierwszy z nich zawiera jedną liczbę całkowitą ,
równą liczbie żetonów.
Każdy z dwóch następnych wierszy zawiera opis zestawu żetonów
w postaci ciągu liczb całkowitych z przedziału ,
pooddzielanych pojedynczymi odstępami;
-ty wyraz ciągu oznacza numer żetonu, na który mają skakać pchły
z żetonu nr .
Wyjście
Dla każdego z przypadków testowych ze standardowego wejścia należy
wypisać na standardowe wyjście dokładnie jeden wiersz,
zawierający dokładnie jedną literę:
- "T" -
jeśli oba zestawy żetonów można ułożyć tak,
aby pchły wykonały taki sam taniec,
- "N" - w przeciwnym wypadku.
Przykład
Dla danych wejściowych:
2
3
2 3 1
2 3 3
4
2 3 2 4
1 3 2 3
poprawną odpowiedzią jest:
N
T
Autor zadania: Marcin Sawicki.